package com.linyaonan.leetcode.sword_to_offer._56_1;

/**
 * 一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：nums = [4,1,4,6]
 * 输出：[1,6] 或 [6,1]
 * 示例 2：
 *
 * 输入：nums = [1,2,10,4,1,4,3,3]
 * 输出：[2,10] 或 [10,2]
 *  
 *
 * 限制：
 *
 * 2 <= nums.length <= 10000
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
class Solution {

    /**
     * 首先所有数值异或操作，可以得到 a ^ b
     * 假设这个值为1001，则表示第零位，第三位a，b不同，那么按照这个规则可以将a，b分开为两组
     * @param nums
     * @return
     */
    public int[] singleNumbers(int[] nums) {
        int a = 0;
        for (int num : nums) {
            a ^= num;
        }

        // 找到最后一个1
        int index = 0;
        while ((a & 1) == 0) {
            index++;
            a >>= 1;
        }
        int r1 = 0,r2 = 0;
        for (int num : nums) {
            if ((num >> index & 1) == 1) {
                r1 ^= num;
            } else {
                r2 ^= num;
            }
        }

        return new int[]{r1, r2};
    }
}